/**
 * 兔子数量计算
 * <pre>
 *     古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第四个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
 *     程序分析：兔子的规律为数列1,1,2,3,5,8,13,21....
 * </pre>
 * Created by donghongli on 2017-03-20.
 */
public class RabbitNumber {
    public static void main(String[] args) {
        int month = 40;
        //带有备忘录功能的实现方式
        long start = System.currentTimeMillis();
        int[] monthRabbitNum = new int[month + 1];
        monthRabbitNum[0] = 0;
        monthRabbitNum[1] = 1;
        monthRabbitNum[2] = 1;
        monthRabbitNum[3] = 2;
        int num = getRabbitNumber(month, monthRabbitNum);
        System.out.println(num);
        System.out.println("getRabbitNumber执行时间为" + (System.currentTimeMillis() - start));
        //没有备忘录的实现，数据过大之后，就会堆栈溢出。或者执行时间异常缓慢
        start = System.currentTimeMillis();
        num = sum(month);
        System.out.println(num);
        System.out.println("sum执行时间为" + (System.currentTimeMillis() - start));
    }

    private static int sum(int month) {
        if (month == 1 || month == 2) {
            return 1;
        }
        return sum(month - 1) + sum(month - 2);
    }

    private static int getRabbitNumber(int month, int[] monthRabbitNum) {
        if (monthRabbitNum[month] != 0) {
            return monthRabbitNum[month];
        }
        int number = getRabbitNumber(month - 1, monthRabbitNum) + getRabbitNumber(month - 2, monthRabbitNum);
        monthRabbitNum[month] = number;
        return number;
    }
}
